/**
 * @author VernHe
 * @date 2021年10月26日 14:48
 */
public class Solution_0494 {

    public int findTargetSumWays(int[] nums, int target) {
        int result = 0;
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (target + sum < 0 || target > sum) {
            return result;
        }
        int clos = sum * 2 + 1;
        // dp[i][j]表示 用前i个数得到target为[j-8]的方法
        int[][] dp = new int[nums.length + 1][clos];
        // 初始化，从0个数开始，初始化
        dp[0][sum] = 1;
        for (int row = 0; row < nums.length; row++) {
            for (int col = 0; col < clos; col++) {
                if (dp[row][col] != 0) {
                    // 减去nums中的第row个数
                    dp[row + 1][col - nums[row]] += dp[row][col];
                    // 加上nums中的第row个数
                    dp[row + 1][col + nums[row]] += dp[row][col];
                }
            }
        }

        return dp[nums.length][target + sum];
    }


    public int findTargetSumWays1(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (target + sum < 0 || target > sum) {
            return 0;
        }
        if ((sum + target) % 2 != 0) {
            return 0;
        }
        // 上一个判断保证target不可能是小数
        // 此时的target就是正数只和，示例：target = 3, sum = 5，正数之和=4，负数之和=1
        target = (sum + target) >> 1;

        // 定义dp，dp[i][j] 表示前i个数，组成和为j的方法，dp[i][j] = dp[i-1][j]（不选） + dp[i-1][j-num]（选）
        int[][] dp = new int[nums.length + 1][target + 1];
        // 初始化，不管可以选前几个数，和为0时,都只有一种方法，那就是都不选，也就是一种方法
        dp[0][0] = 1;
        // 下面的方法不可行是因为没有考虑到有很多0的情况，也就是多个0之间组合
//        for (int i = 0; i <= nums.length; i++) {
//            dp[i][0] = 1;
//        }
        //从只能选一个数开始
        for (int clo = 0; clo <= target; clo++) {
            for (int row = 1; row <= nums.length; row++) {
                if (clo >= nums[row - 1]) {
                    // 选择+不选择
                    dp[row][clo] = dp[row - 1][clo] + dp[row -1][clo - nums[row - 1]];
                } else {
                    // 不能选
                    dp[row][clo] = dp[row - 1][clo];
                }
            }
        }
        return dp[nums.length][target];
    }

    public static void main(String[] args) {
//        System.out.println(new Solution_0494().findTargetSumWays1(new int[]{1, 1, 1, 1,1}, 3));
//        System.out.println(new Solution_0494().findTargetSumWays1(new int[]{1000}, -1000));
        System.out.println(new Solution_0494().findTargetSumWays1(new int[]{0,0,0,0,0,0,0,0,1}, 1));
    }
}
